{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Path Sum III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pathSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #路径总和 III"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树的根节点 <code>root</code> ，和一个整数 <code>targetSum</code> ，求该二叉树里节点值之和等于 <code>targetSum</code> 的 <strong>路径</strong> 的数目。</p>\n",
    "\n",
    "<p><strong>路径</strong> 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/04/09/pathsum3-1-tree.jpg\" style=\"width: 452px; \" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>和等于 8 的路径有 3 条，如图所示。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树的节点个数的范围是 <code>[0,1000]</code></li>\n",
    "\t<li><meta charset=\"UTF-8\" /><code>-10<sup>9</sup> <= Node.val <= 10<sup>9</sup></code> </li>\n",
    "\t<li><code>-1000 <= targetSum <= 1000</code> </li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [path-sum-iii](https://leetcode.cn/problems/path-sum-iii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [path-sum-iii](https://leetcode.cn/problems/path-sum-iii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,5,-3,3,2,null,11,3,-2,null,1]\\n8', '[5,4,8,11,null,13,4,7,2,null,null,5,1]\\n22']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, tot: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        if not root:\n",
    "            return ans\n",
    "        \n",
    "        def getPath(node, path):\n",
    "            if node:\n",
    "                if not node.left and not node.right:\n",
    "                    if sum(path) + node.val == tot:\n",
    "                        ans.append(path + [node.val])\n",
    "                else:\n",
    "                    getPath(node.left, path+[node.val])\n",
    "                    getPath(node.right, path+[node.val])\n",
    "                    \n",
    "        getPath(root, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def pathSum(self, root, sum1):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return []\n",
    "        stack,res=[(root,[root.val])],[]\n",
    "        while stack:\n",
    "            temp,val=stack.pop()\n",
    "            if not temp.left and not temp.right:\n",
    "                if sum(val)==sum1:\n",
    "                    res.append(val)\n",
    "            if temp.left:\n",
    "                stack.append((temp.left,val+[temp.left.val]))\n",
    "            if temp.right:\n",
    "                stack.append((temp.right,val+[temp.right.val]))\n",
    "        return res      \n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def search(self, root, sum, tempResult, result):\n",
    "        if not root.left and not root.right:\n",
    "            if sum-root.val != 0:\n",
    "                return\n",
    "            else:\n",
    "                temp = [val for val in tempResult]\n",
    "                temp.append(root.val)\n",
    "                result.append(temp)\n",
    "                return\n",
    "        if root.left:\n",
    "            tempResult.append(root.val)\n",
    "            self.search(root.left, sum-root.val, tempResult, result)\n",
    "            tempResult.pop()   \n",
    "        if root.right:\n",
    "            tempResult.append(root.val)\n",
    "            self.search(root.right, sum-root.val, tempResult, result)\n",
    "            tempResult.pop()\n",
    "            \n",
    "        \n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        tempResult = []\n",
    "        result = []\n",
    "        if not root:\n",
    "            return result\n",
    "        self.search(root, sum, tempResult, result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def dfs(res, stack, cursum, node, target):\n",
    "            if not node:\n",
    "                return res\n",
    "            cursum += node.val\n",
    "            stack.append(node.val)\n",
    "            if not node.left and not node.right and cursum == target:\n",
    "                res.append(stack[:])\n",
    "            res = dfs(res, stack, cursum, node.left, target)\n",
    "            res = dfs(res, stack, cursum, node.right, target)\n",
    "            stack.pop()\n",
    "            return res\n",
    "        return dfs([], [], 0, root, sum)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root, sum_):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        \n",
    "        def getpaths(root):\n",
    "            if not root: return None\n",
    "            if not root.left and not root.right: return [[root.val]]\n",
    "            lft = getpaths(root.left)\n",
    "            rht = getpaths(root.right)\n",
    "            res = []\n",
    "            if lft:\n",
    "                for x in lft: x.append(root.val)\n",
    "                res.extend(lft)\n",
    "            if rht:\n",
    "                for x in rht: x.append(root.val)\n",
    "                res.extend(rht)\n",
    "            return res\n",
    "        \n",
    "        \n",
    "        res = []\n",
    "        if not root: return res\n",
    "        \n",
    "        for x in getpaths(root):\n",
    "            if sum(x) == sum_:\n",
    "                res.append(x[::-1])\n",
    "        \n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def pathSum(self, root, sum1):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return []\n",
    "        stack=[(root,[root.val])]\n",
    "        res=[]\n",
    "        while stack:\n",
    "            root,onepath=stack.pop()\n",
    "            print(sum(onepath))\n",
    "            if sum(onepath)==sum1 and root.left==None and root.right==None:\n",
    "                res.append(onepath)\n",
    "            if root.right:\n",
    "                stack.append((root.right,onepath+[root.right.val]))\n",
    "            if root.left:\n",
    "                stack.append((root.left,onepath+[root.left.val]))\n",
    "        return res\n",
    "        # stack,res=[(root,[root.val])],[]\n",
    "        # while stack:\n",
    "        #     temp,val=stack.pop()\n",
    "        #     if not temp.left and not temp.right:\n",
    "        #         if sum(val)==sum1:\n",
    "        #             res.append(val)\n",
    "        #     if temp.left:\n",
    "        #         stack.append((temp.left,val+[temp.left.val]))\n",
    "        #     if temp.right:\n",
    "        #         stack.append((temp.right,val+[temp.right.val]))\n",
    "        # return res\n",
    "                \n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        res = []                 \n",
    "        temp = []             \n",
    "\n",
    "        def getPath(node,nowNum):\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            nowNum += node.val\n",
    "            temp.append(node.val)\n",
    "\n",
    "            if not node.left and not node.right and nowNum==sum:\n",
    "                res.append(temp.copy())\n",
    "                temp.pop()\n",
    "                return\n",
    "\n",
    "            getPath(node.left,nowNum)\n",
    "            getPath(node.right,nowNum)\n",
    "            temp.pop()\n",
    "\n",
    "        getPath(root,0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return []\n",
    "        self.ans=[]\n",
    "        self.dfs(root,sum,[])\n",
    "        return self.ans\n",
    "    def dfs(self,p,sum,tmp):\n",
    "        if p is None and sum==0:\n",
    "            self.ans.append(tmp)\n",
    "        elif not p:\n",
    "            return\n",
    "        elif not p.left:\n",
    "            self.dfs(p.right,sum-p.val,tmp+[p.val])\n",
    "        elif not p.right:\n",
    "            self.dfs(p.left,sum-p.val,tmp+[p.val])\n",
    "        else:\n",
    "            self.dfs(p.right,sum-p.val,tmp+[p.val])\n",
    "            self.dfs(p.left,sum-p.val,tmp+[p.val])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def helper(self, root, sum, curr_path, paths):\n",
    "        \n",
    "        if root == None:\n",
    "            return\n",
    "        \n",
    "        path = curr_path + [root.val]\n",
    "        if root.left == None and root.right == None:\n",
    "            if root.val == sum:\n",
    "                paths.append(path)\n",
    "            return\n",
    "        self.helper(root.left, sum-root.val, path, paths)\n",
    "        self.helper(root.right, sum-root.val, path, paths)\n",
    "    \n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        paths = []\n",
    "        path = []\n",
    "        self.helper(root, sum, path, paths)\n",
    "        return paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        l = []\n",
    "        def preorder(root, sum, p, l):\n",
    "            if root.val==sum and not root.left and not root.right:\n",
    "                p.append(root.val)\n",
    "                l.append(p)\n",
    "            if root.left:\n",
    "                preorder(root.left, sum-root.val, p+[root.val], l)\n",
    "            if root.right:\n",
    "                preorder(root.right, sum-root.val, p+[root.val], l)\n",
    "        \n",
    "        if not root:\n",
    "            return []\n",
    "        preorder(root, sum, [], l)\n",
    "        \n",
    "        return l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, target: int):\n",
    "        result = []\n",
    "        dfs(root, target, [], result)\n",
    "        return result\n",
    "\n",
    "\n",
    "def dfs(root: TreeNode, target: int, nums: list, result: list):\n",
    "    if root is None:\n",
    "        return\n",
    "    target -= root.val\n",
    "    nums.append(root.val)\n",
    "    if root.left is None and root.right is None and target == 0:\n",
    "        result.append(nums)\n",
    "        return\n",
    "    dfs(root.left, target, nums[:], result)\n",
    "    dfs(root.right, target, nums[:], result)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    " \n",
    "class Solution(object):\n",
    "    \n",
    "    \n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        self.res=[]\n",
    "        \n",
    "        def help(root,cursum,tmplist):\n",
    "            if not root:\n",
    "                return\n",
    "            tmplist.append(root.val)\n",
    "            cursum+=root.val\n",
    "            if cursum==sum and not root.left and not root.right:\n",
    "                self.res.append(tmplist)\n",
    "            else:\n",
    "                if root.left:\n",
    "                    help(root.left,cursum,tmplist[:])\n",
    "                if root.right:\n",
    "                    help(root.right,cursum,tmplist[:])\n",
    "                \n",
    "            \n",
    "            \n",
    "            \n",
    "        help(root,0,[])  \n",
    "        return self.res\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def searchList(root, mylist, sum, target):\n",
    "            if root is None :\n",
    "                return None\n",
    "            newSum = root.val + sum\n",
    "            newList = []\n",
    "            newList += mylist\n",
    "            newList.append(root.val)\n",
    "            if (root.left is None) and (root.right is None):\n",
    "                if newSum == target:\n",
    "                    return newList\n",
    "                else:\n",
    "                    return None\n",
    "            else:\n",
    "                retList = []\n",
    "                retLeft = searchList(root.left,newList,newSum,target)\n",
    "                retRight = searchList(root.right,newList,newSum,target)\n",
    "                if retLeft is None:\n",
    "                    retList += []\n",
    "                elif isinstance(retLeft[0],list):\n",
    "                    for i in range(len(retLeft)):\n",
    "                        retList.append(retLeft[i])\n",
    "                else:\n",
    "                    retList.append(retLeft)\n",
    "                if retRight is None:\n",
    "                    retList += []\n",
    "                elif isinstance(retRight[0],list):\n",
    "                    for i in range(len(retRight)):\n",
    "                        retList.append(retRight[i])\n",
    "                else:\n",
    "                    retList.append(retRight)\n",
    "                if len(retList) == 0:\n",
    "                    return None\n",
    "                return retList\n",
    "        ret = searchList(root,[],0,sum)\n",
    "        if ret is None:\n",
    "            return []\n",
    "        elif isinstance(ret[0],int):\n",
    "            return [ret]\n",
    "        else:\n",
    "            return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum_: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        stack = [([root.val], root)]\n",
    "        res = []\n",
    "        while stack:\n",
    "            tmp, node = stack.pop()\n",
    "            if not node.right and not node.left and sum(tmp) == sum_:\n",
    "                res.append(tmp)\n",
    "            if node.right:\n",
    "                stack.append((tmp + [node.right.val], node.right))\n",
    "            if node.left:\n",
    "                stack.append((tmp + [node.left.val], node.left))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum_: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return None\n",
    "        stack = [([root.val], root)]#栈存储值的列表和节点\n",
    "        res = []\n",
    "        while stack:\n",
    "            tmp, node = stack.pop()\n",
    "            if not node.left and not node.right and sum(tmp) == sum_:\n",
    "                res.append(tmp)\n",
    "            if node.left:\n",
    "                stack.append((tmp + [node.left.val], node.left))\n",
    "            if node.right:\n",
    "                stack.append((tmp + [node.right.val], node.right))\n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    \"迭代 O（logn）\"\n",
    "    def pathSum(self, root: TreeNode, sum_: int):\n",
    "        if not root:\n",
    "            return []\n",
    "        stack=[([root.val],root)]\n",
    "        res=[]\n",
    "        while stack:\n",
    "            tmp,node=stack.pop()\n",
    "            if not node.left  and not node.right and sum(tmp)==sum_:\n",
    "                res.append(tmp)\n",
    "            if node.right:\n",
    "                stack.append((tmp+[node.right.val],node.right))\n",
    "            if node.left:\n",
    "                stack.append((tmp+[node.left.val],node.left))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # Definition for a binary tree node.\n",
    "# # class TreeNode:\n",
    "# #     def __init__(self, x):\n",
    "# #         self.val = x\n",
    "# #         self.left = None\n",
    "# #         self.right = None\n",
    "\n",
    "# class Solution:\n",
    "#     def pathSum(self, root: TreeNode, total: int) -> List[List[int]]:\n",
    "#         ret = list()\n",
    "#         path = list()\n",
    "        \n",
    "#         def dfs(root: TreeNode, total: int):\n",
    "#             if not root:\n",
    "#                 return\n",
    "#             path.append(root.val)\n",
    "#             total -= root.val\n",
    "#             if not root.left and not root.right and total == 0:\n",
    "#                 ret.append(path[:])\n",
    "#             dfs(root.left, total)\n",
    "#             dfs(root.right, total)\n",
    "#             path.pop()\n",
    "        \n",
    "#         dfs(root, total)\n",
    "#         return ret\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, total: int) -> List[List[int]]:\n",
    "        ret = list()\n",
    "        parent = collections.defaultdict(lambda: None)\n",
    "\n",
    "        def getPath(node: TreeNode):\n",
    "            tmp = list()\n",
    "            while node:\n",
    "                tmp.append(node.val)\n",
    "                node = parent[node]\n",
    "            ret.append(tmp[::-1])\n",
    "\n",
    "        if not root:\n",
    "            return ret\n",
    "        \n",
    "        que_node = collections.deque([root])\n",
    "        que_total = collections.deque([0])\n",
    "\n",
    "        while que_node:\n",
    "            node = que_node.popleft()\n",
    "            rec = que_total.popleft() + node.val\n",
    "\n",
    "            if not node.left and not node.right:\n",
    "                if rec == total:\n",
    "                    getPath(node)\n",
    "            else:\n",
    "                if node.left:\n",
    "                    parent[node.left] = node\n",
    "                    que_node.append(node.left)\n",
    "                    que_total.append(rec)\n",
    "                if node.right:\n",
    "                    parent[node.right] = node\n",
    "                    que_node.append(node.right)\n",
    "                    que_total.append(rec)\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:\n",
    "        ret = list()\n",
    "        parent = collections.defaultdict(lambda: None)\n",
    "\n",
    "        if not root:\n",
    "            return ret\n",
    "\n",
    "        def getPath(node: TreeNode):\n",
    "            tmp = list()\n",
    "            while node:\n",
    "                tmp.append(node.val)\n",
    "                node = parent[node]\n",
    "            ret.append(tmp[::-1])\n",
    "\n",
    "        que_node = collections.deque([root])\n",
    "        que_total = collections.deque([0])\n",
    "        while que_node:\n",
    "            node = que_node.popleft()\n",
    "            rec = que_total.popleft() + node.val\n",
    "            if not node.left and not node.right:\n",
    "                if rec == sum:\n",
    "                    getPath(node)\n",
    "            else:\n",
    "                if node.left:\n",
    "                    parent[node.left] = node\n",
    "                    que_node.append(node.left)\n",
    "                    que_total.append(rec)\n",
    "                if node.right:\n",
    "                    parent[node.right] = node\n",
    "                    que_node.append(node.right)\n",
    "                    que_total.append(rec)\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode-cn.com/problems/path-sum-ii/\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        if not root.left and not root.right:\n",
    "            return [[sum]] if root.val == sum else []\n",
    "        res = []\n",
    "        cur = collections.deque()\n",
    "        cur.append((root, [root.val], root.val))\n",
    "        while cur:\n",
    "            node, path, path_sum = cur.popleft()\n",
    "            if not node.left and not node.right and path_sum == sum:\n",
    "                res.append(path)                \n",
    "            if node.left:\n",
    "                cur.append((node.left, path + [node.left.val], path_sum + node.left.val))\n",
    "            if node.right:\n",
    "                cur.append((node.right, path + [node.right.val], path_sum + node.right.val))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:\n",
    "        # bfs \n",
    "        from collections import deque\n",
    "        if not root:\n",
    "            return []\n",
    "        res = []\n",
    "        q = deque()\n",
    "        sumc = 0\n",
    "        path = []\n",
    "        q.append((sumc, root, path))\n",
    "        while q:\n",
    "            sumc, node, path = q.popleft()\n",
    "            if sumc + node.val == sum and (not node.left and not node.right):\n",
    "                res.append(path + [node.val])\n",
    "            if node.left:\n",
    "                q.append((sumc + node.val, node.left, path+ [node.val]))\n",
    "            if node.right:\n",
    "                q.append((sumc + node.val, node.right, path+ [node.val]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:\n",
    "        path = []\n",
    "        result = []\n",
    "        \n",
    "        def DFS(node, value):\n",
    "            if not node: #空节点不处理\n",
    "                return\n",
    "            path.append(node.val) #记录路径\n",
    "            value -= node.val #计算剩余数值\n",
    "            if node.left or node.right:  #并非叶子节点\n",
    "                DFS(node.left, value) #左子树\n",
    "                DFS(node.right, value) #右子树\n",
    "            elif value == 0:\n",
    "                result.append(path[:])   #路径和为sum，记录结果\n",
    "            path.pop()      #返回上一个节点\n",
    "\n",
    "        DFS(root,sum)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        def getpath(root, parent):\n",
    "            path = []\n",
    "            while root:\n",
    "                path.append(root.val)\n",
    "                root = parent[root]\n",
    "            return path[::-1]\n",
    "\n",
    "        if not root: return []\n",
    "        res = []\n",
    "        que_node = collections.deque([root])\n",
    "        que_val = collections.deque([root.val])\n",
    "        parent = {}\n",
    "        parent[root] = None\n",
    "        while que_node:\n",
    "            node = que_node.popleft()\n",
    "            temp = que_val.popleft()\n",
    "            if not node.left and not node.right and temp == targetSum:\n",
    "                res.append(getpath(node, parent))\n",
    "            if node.left: \n",
    "                parent[node.left] = node\n",
    "                que_node.append(node.left)\n",
    "                que_val.append(temp + node.left.val)\n",
    "            if node.right:\n",
    "                parent[node.right] = node\n",
    "                que_node.append(node.right)\n",
    "                que_val.append(temp + node.right.val)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        st=[(root,targetSum,[root.val])]\n",
    "        re=[]\n",
    "        while st:\n",
    "            cur,value,path=st.pop()\n",
    "            if not cur.left and not cur.right and cur.val==value:\n",
    "                re.append(path)\n",
    "            if cur.right:\n",
    "                tmp=path[:]\n",
    "                tmp.append(cur.right.val)\n",
    "                st.append((cur.right,value-cur.val,tmp))\n",
    "            if cur.left:\n",
    "                tmp=path[:]\n",
    "                tmp.append(cur.left.val)\n",
    "                st.append((cur.left,value-cur.val,tmp))\n",
    "        return re\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        ret = list()\n",
    "        parent = collections.defaultdict(lambda: None)\n",
    "\n",
    "        def getPath(node: TreeNode):\n",
    "            tmp = list()\n",
    "            while node:\n",
    "                tmp.append(node.val)\n",
    "                node = parent[node]\n",
    "            ret.append(tmp[::-1])\n",
    "\n",
    "        if not root:\n",
    "            return ret\n",
    "        \n",
    "        que_node = collections.deque([root])\n",
    "        que_total = collections.deque([0])\n",
    "\n",
    "        while que_node:\n",
    "            node = que_node.popleft()\n",
    "            rec = que_total.popleft() + node.val\n",
    "\n",
    "            if not node.left and not node.right:\n",
    "                if rec == targetSum:\n",
    "                    getPath(node)\n",
    "            else:\n",
    "                if node.left:\n",
    "                    parent[node.left] = node\n",
    "                    que_node.append(node.left)\n",
    "                    que_total.append(rec)\n",
    "                if node.right:\n",
    "                    parent[node.right] = node\n",
    "                    que_node.append(node.right)\n",
    "                    que_total.append(rec)\n",
    "\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "        result = []\n",
    "        parent = {root: None}\n",
    "\n",
    "        def addPath(node):\n",
    "            path = collections.deque()\n",
    "            while node:\n",
    "                path.appendleft(node.val)\n",
    "                node = parent[node]\n",
    "            result.append(list(path))\n",
    "            return\n",
    "        \n",
    "        deq = collections.deque([(root, targetSum)])\n",
    "        while deq:\n",
    "            x, val = deq.popleft()\n",
    "            val -= x.val\n",
    "            if not x.left and not x.right and val == 0:\n",
    "                addPath(x)\n",
    "            if x.left:\n",
    "                deq.append((x.left, val))\n",
    "                parent[x.left] = x\n",
    "            if x.right:\n",
    "                deq.append((x.right, val))\n",
    "                parent[x.right] = x\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "    \tresult = []\n",
    "    \tnums = []\n",
    "    \tdef backtrace(root, presum, targetSum):\n",
    "    \t\tif not root:\n",
    "    \t\t\treturn \n",
    "    \t\tnums.append(root.val)\n",
    "    \t\tif not root.left and not root.right and presum + root.val == targetSum:\n",
    "    \t\t\tresult.append(nums[:])\n",
    "    \t\tbacktrace(root.left, presum+root.val, targetSum)\n",
    "    \t\tbacktrace(root.right, presum+root.val, targetSum)\n",
    "    \t\tnums.pop()\n",
    "    \tbacktrace(root, 0, targetSum)\n",
    "    \treturn result\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:\n",
    "        ret = list()\n",
    "        path = list()\n",
    "        \n",
    "        def dfs(root: TreeNode, targetSum: int):\n",
    "            if not root:\n",
    "                return\n",
    "            path.append(root.val)\n",
    "            targetSum -= root.val\n",
    "            if not root.left and not root.right and targetSum == 0:\n",
    "                ret.append(path[:])\n",
    "            dfs(root.left, targetSum)\n",
    "            dfs(root.right, targetSum)\n",
    "            path.pop()\n",
    "        \n",
    "        dfs(root, targetSum)\n",
    "        return ret\"\"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "    \tresult = []\n",
    "    \tnums = []\n",
    "    \tdef backtrace(root, nums, presum, targetSum):\n",
    "    \t\tif not root:\n",
    "    \t\t\treturn \n",
    "    \t\tnums.append(root.val)\n",
    "    \t\tif not root.left and not root.right and presum + root.val == targetSum:\n",
    "    \t\t\tresult.append(nums[:])\n",
    "    \t\tbacktrace(root.left, nums, presum+root.val, targetSum)\n",
    "    \t\tbacktrace(root.right, nums, presum+root.val, targetSum)\n",
    "    \t\tnums.pop()\n",
    "    \tbacktrace(root, nums, 0, targetSum)\n",
    "    \treturn result\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:\n",
    "        ret = list()\n",
    "        path = list()\n",
    "        \n",
    "        def dfs(root: TreeNode, targetSum: int):\n",
    "            if not root:\n",
    "                return\n",
    "            path.append(root.val)\n",
    "            targetSum -= root.val\n",
    "            if not root.left and not root.right and targetSum == 0:\n",
    "                ret.append(path[:])\n",
    "            dfs(root.left, targetSum)\n",
    "            dfs(root.right, targetSum)\n",
    "            path.pop()\n",
    "        \n",
    "        dfs(root, targetSum)\n",
    "        return ret\"\"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        if not root: return []\n",
    "        stack = [(root, [root.val])]\n",
    "        ans = []\n",
    "        while stack:\n",
    "            node, path = stack.pop()\n",
    "            if not node.left and not node.right and sum(path) == targetSum: \n",
    "                ans.append(path)\n",
    "            if node.right:\n",
    "                stack.append((node.right, path + [node.right.val]))\n",
    "            if node.left: \n",
    "                stack.append((node.left, path + [node.left.val]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        stack = [(root, root.val, [root.val])]\n",
    "        paths = []\n",
    "\n",
    "        while stack:\n",
    "            node, current_sum, path = stack.pop()\n",
    "\n",
    "            if not node.left and not node.right and current_sum == targetSum:\n",
    "                paths.append(path)\n",
    "\n",
    "            if node.right:\n",
    "                stack.append((node.right, current_sum + node.right.val, path + [node.right.val]))\n",
    "\n",
    "            if node.left:\n",
    "                stack.append((node.left, current_sum + node.left.val, path + [node.left.val]))\n",
    "\n",
    "        return paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        result = []\n",
    "        path = []\n",
    "        if not root:\n",
    "            return result\n",
    "\n",
    "        stack = []\n",
    "        stack.append(root)\n",
    "        stack.append(targetSum - root.val)\n",
    "        path.append(root.val)\n",
    "        stack.append(path)\n",
    "\n",
    "        while stack:\n",
    "            tmp_path = stack.pop()\n",
    "            sum_val = stack.pop()\n",
    "            node = stack.pop()\n",
    "\n",
    "            if not node.left and not node.right and sum_val == 0:\n",
    "                result.append(list(tmp_path))\n",
    "\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "                stack.append(sum_val - node.right.val)\n",
    "                tmp_path.append(node.right.val)\n",
    "                stack.append(list(tmp_path))\n",
    "                tmp_path.pop()\n",
    "\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "                stack.append(sum_val - node.left.val)\n",
    "                tmp_path.append(node.left.val)\n",
    "                stack.append(list(tmp_path))\n",
    "                tmp_path.pop()\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        ans_list = []\n",
    "        ans = []\n",
    "        def backtrack(root, targetSum):           \n",
    "            ans.append(root.val)\n",
    "            if root.left:\n",
    "                backtrack(root.left, targetSum - root.val)\n",
    "            if root.right:\n",
    "                backtrack(root.right, targetSum - root.val)\n",
    "            if not root.left and not root.right and targetSum == root.val:\n",
    "                ans_list.append(ans.copy())\n",
    "            ans.pop()\n",
    "\n",
    "        backtrack(root, targetSum)\n",
    "        return ans_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        if not root:\n",
    "            return res\n",
    "        path = []\n",
    "        self.traverse(root, targetSum, path, res)\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def traverse(self, root: Optional[TreeNode], targetSum: int, path: List, res: List):\n",
    "        if not root:\n",
    "            return\n",
    "        targetSum -= root.val\n",
    "        path.append(root.val)\n",
    "        if not root.left and not root.right:\n",
    "            if targetSum == 0:\n",
    "                res.append(list(path))\n",
    "                return\n",
    "        if root.left:\n",
    "            self.traverse(root.left, targetSum, path, res)\n",
    "            path.pop()\n",
    "        if root.right:\n",
    "            self.traverse(root.right, targetSum, path, res)\n",
    "            path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        def DFSTree(root: TreeNode, path: str, targetSum: int):\n",
    "            if root == None:\n",
    "                return\n",
    "            if root.left == None and root.right == None:\n",
    "                path += str(root.val)\n",
    "                ans = path.split('.')\n",
    "                int_value = [int(x) for x in ans]\n",
    "                if sum(int_value) == targetSum:\n",
    "                    result.append(int_value)               \n",
    "                return\n",
    "            path += str(root.val) + '.'\n",
    "            DFSTree(root.left, path, targetSum)\n",
    "            DFSTree(root.right, path, targetSum)\n",
    "        result = []\n",
    "        DFSTree(root, \"\", targetSum)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        def find_path(root,path):\n",
    "            if root:\n",
    "                path+=str(root.val)\n",
    "                # 如果到叶子结点\n",
    "                if not root.left and not root.right:\n",
    "                    paths.append(path)\n",
    "                else:\n",
    "                    path+=\" \"\n",
    "                    find_path(root.left,path)\n",
    "                    find_path(root.right,path)\n",
    "        paths = []\n",
    "        find_path(root,\"\")\n",
    "        # print(paths)\n",
    "        res = []\n",
    "        for path in paths:\n",
    "            tmplst = path.split()\n",
    "            tmplst = [int(x) for x in tmplst]\n",
    "            if sum(tmplst)==targetSum:\n",
    "                res.append(tmplst)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        paths, path = [], []\n",
    "        print(root)\n",
    "        def dfs(root, tar):\n",
    "            # 异常条件\n",
    "            if not root: return\n",
    "            path.append(root.val)\n",
    "            tar -= root.val\n",
    "            # 结束条件\n",
    "            if not root.left and not root.right and tar == 0:\n",
    "                paths.append(list(path))\n",
    "            dfs(root.left, tar)\n",
    "            dfs(root.right, tar)\n",
    "            path.pop() #?\n",
    "        dfs(root, targetSum)\n",
    "        \n",
    "        return paths\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        # 自顶向下递归\n",
    "        res=[]\n",
    "        path=[]\n",
    "\n",
    "        @cache\n",
    "        def dfs(root,cursum):\n",
    "            if not root:\n",
    "                return\n",
    "            path.append(root.val)\n",
    "            cursum-=root.val\n",
    "            if  (root.left == root.right) and cursum==0:\n",
    "                res.append(path[:])\n",
    "            dfs(root.left,cursum)\n",
    "            dfs(root.right,cursum)\n",
    "            path.pop()\n",
    "\n",
    "        dfs(root,targetSum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        # 自顶向下递归\n",
    "        res=[]\n",
    "        path=[]\n",
    "\n",
    "        @cache\n",
    "        def dfs(root,cursum):\n",
    "            if not root:\n",
    "                return\n",
    "            path.append(root.val)\n",
    "            cursum-=root.val\n",
    "            if  (root.left == root.right) and cursum==0:\n",
    "                res.append(path[:])\n",
    "            dfs(root.left,cursum)\n",
    "            dfs(root.right,cursum)\n",
    "            path.pop()\n",
    "\n",
    "        dfs(root,targetSum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        def dfs(root, val, l):\n",
    "            if(root is None):\n",
    "                return\n",
    "            if(val+root.val == targetSum and root.left is None and root.right is None):\n",
    "                ans.append(l+[root.val])\n",
    "            else:\n",
    "                dfs(root.left, val+root.val, l+[root.val])\n",
    "                dfs(root.right, val+root.val, l+[root.val])\n",
    "        dfs(root, 0, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        def dfs(ans,summ,root,path):\n",
    "            if root is None:\n",
    "                return\n",
    "            if summ-root.val==0 and root.left is None and root.right is None:\n",
    "                return ans.append(path+[root.val])\n",
    "            dfs(ans,summ-root.val,root.left,path+[root.val])\n",
    "            dfs(ans,summ-root.val,root.right,path+[root.val])\n",
    "        ans=[]\n",
    "        if root is None:\n",
    "            return [] \n",
    "        dfs(ans,targetSum,root,[])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        ans=[]\n",
    "        def dfs(root,path,target):\n",
    "            if not root: return\n",
    "            if not root.left and not root.right:\n",
    "                if target==root.val:\n",
    "                    \n",
    "                    path += [root.val]\n",
    "                    ans.append(path)\n",
    "                    return\n",
    "            dfs(root.left,path+[root.val],target-root.val)\n",
    "            dfs(root.right,path+[root.val],target-root.val)\n",
    "        dfs(root,[],targetSum)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        result = []\n",
    "        output = []\n",
    "        path = \"\"\n",
    "        sum_temp = 0\n",
    "        self.TreePaths(root, path, output)\n",
    "        for i in output:\n",
    "            temp = i.split(\"->\")\n",
    "            for j in range(len(temp)):\n",
    "                temp[j] = int(temp[j])           \n",
    "            sum_temp = sum(temp)\n",
    "            if sum_temp == targetSum:\n",
    "                result.append(temp)\n",
    "        return result\n",
    "\n",
    "    def TreePaths(self, root, path, output):\n",
    "        path = path + str(root.val)\n",
    "        if not root.left and not root.right:\n",
    "            output.append(path)\n",
    "\n",
    "        if root.left is not None:\n",
    "            self.TreePaths(root.left, path + \"->\", output)\n",
    "               \n",
    "        if root.right is not None:\n",
    "            self.TreePaths(root.right, path + \"->\", output)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "\n",
    "        routes=[]\n",
    "        route=[]\n",
    "        def search(node,routes,route,target):\n",
    "            if not node:\n",
    "                return\n",
    "            route.append(node.val)\n",
    "            target-=node.val\n",
    "            if not node.left and not node.right:\n",
    "                if target==0:\n",
    "                    routes.append(route)\n",
    "            \n",
    "            search(node.left,routes,route.copy(),target)\n",
    "            search(node.right,routes,route.copy(),target)\n",
    "        \n",
    "        search(root,routes,route,targetSum)\n",
    "\n",
    "        return routes\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    output = []\n",
    "    \n",
    "    def dfs(self, node, target, currentList):\n",
    "        if node:\n",
    "            # currentList.append(node.val)\n",
    "            l = currentList + [node.val]\n",
    "            if not node.left and not node.right:\n",
    "                if target == node.val:\n",
    "                    self.output.append(l)\n",
    "            else: \n",
    "                if node.left:\n",
    "                    self.dfs(node.left, target - node.val, l)\n",
    "                if node.right:\n",
    "                    self.dfs(node.right, target - node.val, l)\n",
    "        \n",
    "\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        l = []\n",
    "        self.output = []\n",
    "        self.dfs(root, targetSum, l)\n",
    "        return self.output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\n",
    "        if not root:\n",
    "            return []\n",
    "\n",
    "        self.ans = []\n",
    "        self.traversal(root, [], targetSum)\n",
    "\n",
    "        return self.ans\n",
    "    \n",
    "    def traversal(self, root, path, count):\n",
    "        # if not root:\n",
    "        #     return \n",
    "        count -= root.val\n",
    "        path = path + [root.val]\n",
    "\n",
    "        if not root.left and not root.right:\n",
    "            if count == 0:\n",
    "                self.ans.append(path)\n",
    "            else:\n",
    "                return \n",
    "        \n",
    "        if root.left:\n",
    "            self.traversal(root.left, path, count)\n",
    "        if root.right:\n",
    "            self.traversal(root.right, path, count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:\r\n",
    "        self.res = []\r\n",
    "        if not root:\r\n",
    "            return []\r\n",
    "        self.dfs(root,[],targetSum)\r\n",
    "        return self.res\r\n",
    "    \r\n",
    "    def dfs(self,root,lis,targetSum):\r\n",
    "        tmp = lis + [root.val]\r\n",
    "        if not root.left and not root.right:\r\n",
    "            if sum(tmp) == targetSum:\r\n",
    "                self.res.append(tmp)\r\n",
    "        if root.left:\r\n",
    "            self.dfs(root.left,tmp,targetSum)\r\n",
    "        if root.right:\r\n",
    "            self.dfs(root.right,tmp,targetSum)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        return self.findPathSum(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)\n",
    "        \n",
    "        \n",
    "    def findPathSum(self, node, total):\n",
    "        if not node:\n",
    "            return 0\n",
    "        \n",
    "        return (1 if node.val == total else 0) + self.findPathSum(node.left, total - node.val) + self.findPathSum(node.right, total - node.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\r\n",
    "# @lc app=leetcode.cn id=437 lang=python3\r\n",
    "#\r\n",
    "# [437] 路径总和 III\r\n",
    "#\r\n",
    "# https://leetcode-cn.com/problems/path-sum-iii/description/\r\n",
    "#\r\n",
    "# algorithms\r\n",
    "# Easy (46.25%)\r\n",
    "# Total Accepted:    3K\r\n",
    "# Total Submissions: 6.6K\r\n",
    "# Testcase Example:  '[10,5,-3,3,2,null,11,3,-2,null,1]\\n8'\r\n",
    "#\r\n",
    "# 给定一个二叉树，它的每个结点都存放着一个整数值。\r\n",
    "#\r\n",
    "# 找出路径和等于给定数值的路径总数。\r\n",
    "#\r\n",
    "# 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。\r\n",
    "#\r\n",
    "# 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。\r\n",
    "#\r\n",
    "# 示例：\r\n",
    "#\r\n",
    "# root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8\r\n",
    "#\r\n",
    "# ⁠     10\r\n",
    "# ⁠    /  \\\r\n",
    "# ⁠   5   -3\r\n",
    "# ⁠  / \\    \\\r\n",
    "# ⁠ 3   2   11\r\n",
    "# ⁠/ \\   \\\r\n",
    "# 3  -2   1\r\n",
    "#\r\n",
    "# 返回 3。和等于 8 的路径有:\r\n",
    "#\r\n",
    "# 1.  5 -> 3\r\n",
    "# 2.  5 -> 2 -> 1\r\n",
    "# 3.  -3 -> 11\r\n",
    "#\r\n",
    "#\r\n",
    "#\r\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.left = None\r\n",
    "#         self.right = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def pathSum(self, root, sum):\r\n",
    "        \"\"\"\r\n",
    "        :type root: TreeNode\r\n",
    "        :type sum: int\r\n",
    "        :rtype: int\r\n",
    "        \"\"\"\r\n",
    "        if root == None:\r\n",
    "            return 0\r\n",
    "        cnt = 0\r\n",
    "        if sum == root.val:\r\n",
    "            cnt += 1\r\n",
    "        queue = [[root, [sum - root.val]]]\r\n",
    "\r\n",
    "        while queue:\r\n",
    "            node, arr = queue.pop()\r\n",
    "\r\n",
    "            for tmp in [node.left, node.right]:\r\n",
    "                tmp_arr = []\r\n",
    "                if tmp:\r\n",
    "                    tmp_arr = [i - tmp.val for i in arr]\r\n",
    "                    tmp_arr.append(sum - tmp.val)\r\n",
    "                    for i in tmp_arr:\r\n",
    "                        if i == 0:\r\n",
    "                            cnt += 1\r\n",
    "                    queue.append([tmp, tmp_arr])\r\n",
    "\r\n",
    "        return cnt\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __help(self, n):\n",
    "        if n:\n",
    "            self.__path.appendleft(n.val)\n",
    "            for i in itertools.accumulate(self.__path):\n",
    "                if i == self.__sum:\n",
    "                    self.__cnt += 1\n",
    "            self.__help(n.left)\n",
    "            self.__help(n.right)\n",
    "            self.__path.popleft()\n",
    "\n",
    "    def pathSum(self, root, sumVal):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.__cnt, self.__path, self.__sum = 0, collections.deque(), sumVal\n",
    "        self.__help(root)\n",
    "        return self.__cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return 0\n",
    "        total = 0\n",
    "        total += self.pathSumRecursive(root, sum)\n",
    "        if root.left:\n",
    "            total += self.pathSum(root.left, sum)\n",
    "        if root.right:\n",
    "            total += self.pathSum(root.right, sum)\n",
    "        return total\n",
    "\n",
    "    def pathSumRecursive(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        total = 0\n",
    "        if root.val == sum:\n",
    "            total += 1\n",
    "        if root.left:\n",
    "            total += self.pathSumRecursive(root.left, sum - root.val)\n",
    "        if root.right:\n",
    "            total += self.pathSumRecursive(root.right, sum - root.val)\n",
    "\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution(object):\n",
    "    def helper(self, root, target, so_far, cache):\n",
    "        if root:\n",
    "            complement = so_far + root.val - target\n",
    "            if complement in cache:\n",
    "                self.result += cache[complement]\n",
    "            cache.setdefault(so_far+root.val, 0)\n",
    "            cache[so_far+root.val] += 1\n",
    "            self.helper(root.left, target, so_far+root.val, cache)\n",
    "            self.helper(root.right, target, so_far+root.val, cache)\n",
    "            cache[so_far+root.val] -= 1\n",
    "        return\n",
    "\n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        self.result = 0\n",
    "        self.helper(root, sum, 0, {0:1})\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def findpath(root, sum):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if root.val == sum:\n",
    "                res += 1\n",
    "            res += findpath(root.left, sum-root.val)\n",
    "            res += findpath(root.right, sum-root.val)\n",
    "            return res\n",
    "        \n",
    "        if root is None:\n",
    "            return 0\n",
    "        res = findpath(root, sum)\n",
    "        res += self.pathSum(root.left, sum)\n",
    "        res += self.pathSum(root.right, sum)\n",
    "        # if root.left:\n",
    "        #     res = res + self.pathSum(root.left, sum-root.val) + self.pathSum(root.left, sum)\n",
    "        # if root.right:\n",
    "        #     res = res + self.pathSum(root.right, sum-root.val) + self.pathSum(root.right, sum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: 'TreeNode', sum: 'int') -> 'int':\n",
    "#         from collections import defaultdict\n",
    "#         lookup = defaultdict(int)\n",
    "#         lookup[0] = 1\n",
    "#         self.res = 0\n",
    "        \n",
    "#         def helper(root,curSum):\n",
    "#             if not root:\n",
    "#                 return \n",
    "#             curSum += root.val\n",
    "#             self.res += lookup[curSum - sum]\n",
    "#             lookup[curSum] += 1\n",
    "#             helper(root.left,curSum)\n",
    "#             helper(root.right,curSum)\n",
    "#             lookup[curSum] -= 1\n",
    "#         helper(root,0)\n",
    "#         return self.res\n",
    "        path = []\n",
    "        def dfs(r, p, s):\n",
    "            if not r:\n",
    "                return 0\n",
    "            p.append(0)\n",
    "            for i in range(len(p)):\n",
    "                p[i] += r.val\n",
    "            ans = p.count(s) + dfs(r.left, p, s) + dfs(r.right, p, s)\n",
    "            p.pop()\n",
    "            for i in range(len(p)):\n",
    "                p[i] -= r.val\n",
    "            #print(r.val, ans)\n",
    "            return ans\n",
    "        return dfs(root, path, sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: 'TreeNode', sum: 'int') -> 'int':\n",
    "        self.ret = 0\n",
    "        self.sum = sum\n",
    "        ls = []\n",
    "        ls.append(0)\n",
    "        self.func(root,ls)\n",
    "        return self.ret\n",
    "    def func(self,root,ls):\n",
    "        if root==None:\n",
    "            return\n",
    "        ls.append(ls[-1]+root.val)\n",
    "        ln = len(ls)\n",
    "        i = ln - 2\n",
    "        while i>=0:\n",
    "            if ls[-1] - ls[i] == self.sum:\n",
    "                self.ret += 1\n",
    "            i -= 1\n",
    "        self.func(root.left,ls)\n",
    "        self.func(root.right,ls)\n",
    "        ls.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root, sum):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type sum: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        if not root:\n",
    "            return 0 \n",
    "        return self.dfs(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)\n",
    "\n",
    "\n",
    "    def dfs(self, root, target):\n",
    "        res = 0\n",
    "        if not root:\n",
    "            return res\n",
    "        target -= root.val\n",
    "        if target == 0:\n",
    "            res += 1\n",
    "        res += self.dfs(root.left, target)\n",
    "        res += self.dfs(root.right, target)\n",
    "        return res\n",
    "        \n",
    "    def helper(self, root, target):\n",
    "        if target == 0:\n",
    "            self.res += 1\n",
    "            return\n",
    "        if not root:\n",
    "            return\n",
    "        if target == 0:\n",
    "            self.res += 1\n",
    "        self.helper(root.left, target - root.val)\n",
    "        self.helper(root.right, target - root.val)\n",
    "    \n",
    "    def traversal(self, root, target):\n",
    "        if not root:\n",
    "            return\n",
    "        self.helper(root, target)\n",
    "        self.pathSum(root.left, target)\n",
    "        self.pathSum(root.right, target)\n",
    "\n",
    "        return self.res\n",
    "            \n",
    "        \n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        num = 0\n",
    "        \n",
    "        if root:\n",
    "            stack = [(root, [sum - root.val])]\n",
    "            while stack:\n",
    "                node, sums = stack.pop()\n",
    "                for sum_ in sums:\n",
    "                    if sum_ == 0:\n",
    "                        num += 1\n",
    "                if node.left:\n",
    "                    stack.append((node.left, [sum_ - node.left.val for sum_ in sums] + [sum - node.left.val]))\n",
    "                if node.right:\n",
    "                    stack.append((node.right, [sum_ - node.right.val for sum_ in sums] + [sum - node.right.val]))\n",
    "        \n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if not root: return 0\n",
    "        stack = [(root, [root.val])]\n",
    "        res = 0\n",
    "        while stack:\n",
    "            node, tmp = stack.pop()\n",
    "            res += tmp.count(sum)\n",
    "            tmp+=[0]\n",
    "            if node.left:\n",
    "                arr = [i + node.left.val for i in tmp]\n",
    "                stack.append((node.left, arr))\n",
    "            if node.right:\n",
    "                arr= [i + node.right.val for i in tmp]\n",
    "                stack.append((node.right, arr))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum_: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        stack = [(root, [0, root.val])]\n",
    "        res = 0\n",
    "        while stack:\n",
    "            node, path = stack.pop()\n",
    "            for p in path[:-1]:\n",
    "                if path[-1] - p == sum_:\n",
    "                    res += 1\n",
    "                    continue\n",
    "            if node.left:\n",
    "                stack.append((node.left, path+[path[-1]+node.left.val]))\n",
    "            if node.right:\n",
    "                stack.append((node.right, path+[path[-1]+node.right.val]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum1(self, root: TreeNode, sum: int) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        tmp = 0\n",
    "        if sum == root.val:\n",
    "            tmp = 1\n",
    "        return self.pathSum1(root.left, sum - root.val) + self.pathSum1(root.right, sum - root.val) + tmp\n",
    "\n",
    "    # def pathSum2(self, root: TreeNode, sum: int) -> int:\n",
    "    #     if root == None:\n",
    "    #         return 0\n",
    "    #     if sum == root.val:\n",
    "    #         return 1\n",
    "    #     return self.pathSum2(root.left, sum) + self.pathSum2(root.right, sum)\n",
    "\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "\n",
    "        return self.pathSum(root.left, sum) + self.pathSum(root.right, sum) + self.pathSum1(root, sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import Counter\n",
    "\n",
    "def dfs(root, target):\n",
    "    stack = [(root, 0)] if root else []\n",
    "    path = []\n",
    "    cnt = Counter()\n",
    "    res = 0\n",
    "    while stack:\n",
    "        x = stack.pop()\n",
    "        if x is None:\n",
    "            cnt[path.pop()] -= 1\n",
    "            continue\n",
    "        node, s = x\n",
    "        s += node.val\n",
    "        if s == target:\n",
    "            res += 1\n",
    "        res += cnt[s - target]\n",
    "        path.append(s)\n",
    "        cnt[s] += 1\n",
    "        if not node.left and not node.right:\n",
    "            cnt[path.pop()] -= 1\n",
    "        else:\n",
    "            stack.append(None)\n",
    "            if node.left:\n",
    "                stack.append((node.left, s))\n",
    "            if node.right:\n",
    "                stack.append((node.right, s))\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        return dfs(root, targetSum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        if not root:return 0\n",
    "        stack=[root]\n",
    "        stack_dic=[{0:1}]\n",
    "        stack_sum=[0]\n",
    "        res=0\n",
    "        while stack:\n",
    "            tmp=stack.pop()\n",
    "            tmp_dic=stack_dic.pop()\n",
    "            tmp_sum=stack_sum.pop()\n",
    "            tmp_sum+=tmp.val\n",
    "            if tmp_sum-targetSum in tmp_dic:\n",
    "                res+=tmp_dic[tmp_sum-targetSum]\n",
    "            tmp_dic[tmp_sum]=tmp_dic.get(tmp_sum,0)+1\n",
    "            if tmp.left:\n",
    "                stack.append(tmp.left)\n",
    "                stack_sum.append(tmp_sum)\n",
    "                stack_dic.append(tmp_dic.copy())\n",
    "            if tmp.right:\n",
    "                stack.append(tmp.right)\n",
    "                stack_sum.append(tmp_sum)\n",
    "                stack_dic.append(tmp_dic.copy())\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "\n",
    "        queue = collections.deque()\n",
    "        if not root: return 0\n",
    "        queue.append((root,root.val,[0]))\n",
    "        count = 0\n",
    "        while queue:\n",
    "            node, path, before = queue.popleft()\n",
    "            for x in before:\n",
    "                if path - x == targetSum:\n",
    "                    count +=1\n",
    "            if node.right:\n",
    "                queue.append((node.right,path+node.right.val,before+[path]))\n",
    "            if node.left:\n",
    "                queue.append((node.left,path+node.left.val,before+[path]))\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        visited = {root}\n",
    "        value_cnt = {0:1}\n",
    "        value_cnt[root.val] = value_cnt.get(root.val, 0) + 1\n",
    "        st = [(root, root.val)]\n",
    "        res = 0\n",
    "        while st:\n",
    "            if st[-1][0].left and st[-1][0].left not in visited:\n",
    "                st.append((st[-1][0].left, st[-1][1] + st[-1][0].left.val))\n",
    "                value_cnt[st[-1][1]] = value_cnt.get(st[-1][1], 0) + 1\n",
    "                visited.add(st[-1][0])\n",
    "                continue\n",
    "            if st[-1][0].right and st[-1][0].right not in visited:\n",
    "                st.append((st[-1][0].right, st[-1][1] + st[-1][0].right.val))\n",
    "                value_cnt[st[-1][1]] = value_cnt.get(st[-1][1], 0) + 1\n",
    "                visited.add(st[-1][0])\n",
    "                continue\n",
    "            node, val = st.pop()\n",
    "            value_cnt[val] = value_cnt.get(val) - 1 \n",
    "            res += value_cnt.get(val - targetSum, 0)\n",
    "            \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        q = [(root, [root.val])]\n",
    "        res = 0\n",
    "        while q:\n",
    "            count = len(q)\n",
    "            for _ in range(count):\n",
    "                node, node_sums = q.pop(0)\n",
    "                for e in node_sums:\n",
    "                    if e == targetSum:\n",
    "                        res += 1\n",
    "                if node.left:\n",
    "                    left_sums = [e + node.left.val for e in node_sums]\n",
    "                    left_sums.append(node.left.val)\n",
    "                    q.append((node.left, left_sums))\n",
    "                if node.right:\n",
    "                    right_sums = [e + node.right.val for e in node_sums]\n",
    "                    right_sums.append(node.right.val)\n",
    "                    q.append((node.right, right_sums))\n",
    "        return res \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "            \n",
    "        ret = self.rootSum(root, targetSum)\n",
    "        ret += self.pathSum(root.left, targetSum)\n",
    "        ret += self.pathSum(root.right, targetSum)\n",
    "        return ret\n",
    "\n",
    "\n",
    "    def rootSum(self, root, targetSum):\n",
    "        if root is None:\n",
    "            return 0\n",
    "\n",
    "        ret = 0\n",
    "        if root.val == targetSum:\n",
    "            ret += 1\n",
    "\n",
    "        ret += self.rootSum(root.left, targetSum - root.val)\n",
    "        ret += self.rootSum(root.right, targetSum - root.val)\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        def rootsum(root, targetSum):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            \n",
    "            ret = 0\n",
    "            if root.val == targetSum:\n",
    "                ret += 1\n",
    "            \n",
    "            ret += rootsum(root.left, targetSum - root.val)\n",
    "            ret += rootsum(root.right, targetSum - root.val)\n",
    "\n",
    "            return ret\n",
    "        \n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        ret = rootsum(root, targetSum)\n",
    "\n",
    "        ret += self.pathSum(root.left, targetSum)\n",
    "        ret += self.pathSum(root.right, targetSum)\n",
    "\n",
    "        return ret\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        def nums(root: TreeNode, n):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            s = 0\n",
    "            if root.val == n:\n",
    "                s += 1\n",
    "            return s + nums(root.left, n-root.val) + nums(root.right, n-root.val)\n",
    "        if root is None:\n",
    "            return 0\n",
    "        return nums(root, targetSum) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    ans = 0\n",
    "    originalTargetSum = 0\n",
    "    markedBegin = set()\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        self.originalTargetSum = targetSum\n",
    "        self.dfs(root, targetSum)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self, root, targetSum):\n",
    "        # 计算以该节点为头的路径数目\n",
    "        \n",
    "            \n",
    "        if not root:\n",
    "            return \n",
    "\n",
    "        if targetSum == root.val:\n",
    "            # print(root.val)\n",
    "            self.ans += 1\n",
    "        \n",
    "        self.dfs(root.left, targetSum - root.val)\n",
    "        self.dfs(root.right, targetSum - root.val)\n",
    "        if not root.left in self.markedBegin:\n",
    "            self.dfs(root.left, self.originalTargetSum)\n",
    "            self.markedBegin.add(root.left)\n",
    "        if not root.right in self.markedBegin:\n",
    "            self.dfs(root.right, self.originalTargetSum)\n",
    "            self.markedBegin.add(root.right)\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "import copy\n",
    "from collections import deque\n",
    "from functools import lru_cache\n",
    "null = None\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def build_tree(self, nums):\n",
    "        root = TreeNode(nums.pop(0))\n",
    "        q = deque([])\n",
    "        q.append(root)\n",
    "        while q and nums:\n",
    "            node = q.popleft()\n",
    "            l_v = nums.pop(0)\n",
    "            if l_v is not None:\n",
    "                node.left = TreeNode(l_v)\n",
    "                q.append(node.left)\n",
    "            if nums:\n",
    "                r_v = nums.pop(0)\n",
    "                if r_v is not None:\n",
    "                    node.right = TreeNode(r_v)\n",
    "                    q.append(node.right)\n",
    "        return root\n",
    "\n",
    "    def pathSum(self, root, targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = 0\n",
    "        fa = deque([])\n",
    "        stack = [(root, fa)]\n",
    "        @lru_cache(None)\n",
    "        def sons_fas(son_val, fa) -> int:\n",
    "            ans, s = 0, son_val\n",
    "            if s == targetSum:\n",
    "                ans += 1\n",
    "            for f in fa:\n",
    "                s += f\n",
    "                if s == targetSum:\n",
    "                    ans += 1\n",
    "            return ans\n",
    "\n",
    "        while stack:\n",
    "            node, fa_old = stack.pop()\n",
    "            res += sons_fas(node.val, tuple(fa_old))\n",
    "            fa = copy.deepcopy(fa_old)\n",
    "            if fa:\n",
    "                fa.appendleft(node.val)\n",
    "            else:\n",
    "                fa = deque([node.val])\n",
    "            if node.left:\n",
    "                stack.append((node.left, fa))\n",
    "            if node.right:\n",
    "                stack.append((node.right, fa))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        def find(T,c):\n",
    "            if not T :\n",
    "                return 0\n",
    "            cur = c[-1] + T.val\n",
    "            ans = sum(cur - pre == targetSum for pre in c)              \n",
    "            c.append(cur)\n",
    "            return ans + find(T.left,list(c)) + find(T.right,list(c))\n",
    "        return find(root,[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        self.res = 0\n",
    "\n",
    "        def traverse(node, acc, pre_acc):\n",
    "            if not node:\n",
    "                return \n",
    "            acc += node.val\n",
    "\n",
    "            if acc == targetSum:\n",
    "                self.res += 1\n",
    "            for num in pre_acc:\n",
    "                if acc - num == targetSum:\n",
    "                    self.res += 1\n",
    "            traverse(node.left, acc, pre_acc + [acc])\n",
    "            traverse(node.right, acc, pre_acc + [acc])\n",
    "\n",
    "        traverse(root, 0, [])\n",
    "        return self.res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        #深度优先 Dfs\n",
    "        cn=0\n",
    "        if  root is None:\n",
    "            return 0\n",
    "        def  dfs(root,tmp):\n",
    "            \"\"\"\n",
    "            :param tmp: 保存前缀和\n",
    "            :return:统计存在叶子节点和为targetSum的场景的个数\n",
    "            \"\"\"\n",
    "            nonlocal cn\n",
    "            for j in range(len(tmp)-1):\n",
    "                if tmp[-1] - tmp[j] == targetSum:\n",
    "                    # print(tmp[-1], tmp[j])\n",
    "                    cn += 1\n",
    "            if root.left is None and root.right is None:\n",
    "                #此时已经从根节点遍历到某个叶子节点的所有前缀和已经统计到了\n",
    "                #然后针对前缀和，求是否存在targetSum\n",
    "                return\n",
    "            if root.left:\n",
    "                dfs(root.left,tmp+[tmp[-1]+root.left.val])\n",
    "            if root.right:\n",
    "                dfs(root.right, tmp + [tmp[-1] + root.right.val])\n",
    "        dfs(root,[0,root.val])\n",
    "        return cn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        def dfs(node, presum):\n",
    "            if not node :\n",
    "                return 0\n",
    "            cur = presum[-1] + node.val\n",
    "            ans = sum((cur - j) == targetSum  for j in presum)\n",
    "            presum.append(cur)\n",
    "            return ans + dfs(node.right,presum[:])+dfs(node.left,list(presum))\n",
    "        return dfs(root,[0])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        \n",
    "        def dfs(root,path_sum,prefix_sum):\n",
    "            if root == None:\n",
    "                return\n",
    "            path_sum = path_sum + root.val\n",
    "            # prefix_sum = prefix_sum + [path_sum]\n",
    "            for item in prefix_sum:\n",
    "                if path_sum - item == targetSum:\n",
    "                    print(path_sum,item)\n",
    "                    path_num[0] += 1\n",
    "            # if root.val == targetSum:\n",
    "            #     path_num[0] += 1\n",
    "            # print(prefix_sum)\n",
    "            dfs(root.left,path_sum, prefix_sum + [path_sum])\n",
    "            dfs(root.right,path_sum, prefix_sum + [path_sum])\n",
    "            return \n",
    "        path_num = [0]\n",
    "        prefix_sum = [0]\n",
    "        dfs(root,0,prefix_sum)\n",
    "        return path_num[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        if not root: return 0\n",
    "        l = []\n",
    "        self.diedai(root, targetSum, l)\n",
    "        print((l))\n",
    "        return sum(l)\n",
    "        \n",
    "    def diedai(self, root, targetSum, l):\n",
    "        if not root: return \n",
    "        self.find(root, targetSum, l)\n",
    "        self.diedai(root.left, targetSum, l)\n",
    "        self.diedai(root.right, targetSum, l)\n",
    "\n",
    "    def find(self, root, targetSum, l):\n",
    "        # 下面这种写法就是没注意，后面还会有，单节点等于这个值的……\n",
    "        # if not root: return\n",
    "        # if targetSum - root.val == 0:\n",
    "        #     l.append(1)\n",
    "        #     return\n",
    "        # self.find(root.left, targetSum - root.val, l)\n",
    "        # self.find(root.right, targetSum - root.val, l)\n",
    "        if not root: return\n",
    "        if targetSum - root.val == 0:\n",
    "            l.append(1)\n",
    "        self.find(root.left, targetSum - root.val, l)\n",
    "        self.find(root.right, targetSum - root.val, l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        res = 0\n",
    "\n",
    "        dfs = [(root,[0])]\n",
    "\n",
    "        while dfs:\n",
    "            node, prefix = dfs.pop()\n",
    "            if node is None: continue\n",
    "\n",
    "            for p in prefix:\n",
    "                if node.val + prefix[-1] - targetSum == p:\n",
    "                    res += 1\n",
    "            \n",
    "            dfs.append((node.left, prefix+[prefix[-1]+node.val]))\n",
    "            dfs.append((node.right, prefix+[prefix[-1]+node.val]))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        \n",
    "        def Dsf(curNode, curSum, ans = \"\"):\n",
    "            if curNode == None:\n",
    "                return 0\n",
    "            ret = 0\n",
    "            #print(\"%i %i\", (curNode.val, curSum))\n",
    "            if curNode.left == None and curNode.right == None:\n",
    "                #子节点了\n",
    "                if (curSum + curNode.val) == targetSum:\n",
    "                    # print(curSum)\n",
    "                    # print(curNode.val)\n",
    "                    #print(ans + \"|\" + str(curNode.val))\n",
    "                    return 1\n",
    "                return 0\n",
    "\n",
    "            curSum += curNode.val\n",
    "            if curSum == targetSum:\n",
    "                #print(ans + \"|\" + str(curNode.val))\n",
    "                ret += 1\n",
    "            \n",
    "            ans =  ans + \"|\" + str(curSum)\n",
    "            if curNode.left != None:\n",
    "                ret += Dsf(curNode.left, curSum, ans)\n",
    "                #Dsf(curNode.left, 0)\n",
    "            if curNode.right != None:\n",
    "                ret += Dsf(curNode.right, curSum, ans)\n",
    "                #Dsf(curNode.right, 0)\n",
    "            return ret\n",
    "\n",
    "        ans = 0  \n",
    "        ans = Dsf(root, 0)\n",
    "        ans += self.pathSum(root.left, targetSum)\n",
    "        ans += self.pathSum(root.right, targetSum)\n",
    "            \n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        ans = []\n",
    "        def dfs(root,sum_):\n",
    "            \n",
    "            if root.left is None and root.right is None:\n",
    "                sum_ +=root.val\n",
    "                \n",
    "                if sum_ == targetSum:\n",
    "                    ans.append(1)\n",
    "                    \n",
    "            else:\n",
    "                sum_ +=root.val\n",
    "               \n",
    "                if sum_ == targetSum:\n",
    "                    ans.append(1)\n",
    "                if root.left:\n",
    "                    dfs(root.left,sum_)\n",
    "                if root.right:\n",
    "                    dfs(root.right,sum_)\n",
    "            \n",
    "        \n",
    "        def dfs2(root):\n",
    "            if root ==  None:\n",
    "                return 0\n",
    "            else:\n",
    "                \n",
    "                if root.left is None and root.right is None:\n",
    "                    dfs(root,0)\n",
    "                else:\n",
    "                    dfs(root,0)\n",
    "                    if root.left:   \n",
    "                        dfs2(root.left)\n",
    "                    if root.right:\n",
    "                \n",
    "                        dfs2(root.right)\n",
    "\n",
    "        dfs2(root)\n",
    "        return len(ans)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        def dfs(root, presum, presum_dict):\n",
    "            count = 0           \n",
    "            presum.append(presum[-1]+root.val)\n",
    "            print(presum)\n",
    "            count = presum_dict.get(presum[-1]-targetSum, 0)\n",
    "            print('count',count)\n",
    "            presum_dict[presum[-1]] = presum_dict.get(presum[-1], 0) + 1           \n",
    "            if root.left==None and root.right==None:\n",
    "                return count\n",
    "            elif root.right==None:\n",
    "                presum1= copy.copy(presum)\n",
    "                return dfs(root.left, presum1, presum_dict) + count\n",
    "            elif root.left==None:\n",
    "                presum1= copy.copy(presum)\n",
    "                return dfs(root.right, presum1, presum_dict) + count\n",
    "            else:\n",
    "                presum1= copy.copy(presum)\n",
    "                presum2 =copy.copy(presum)\n",
    "                presum_dict1 = copy.copy(presum_dict)\n",
    "                presum_dict2 = copy.copy(presum_dict)\n",
    "                return dfs(root.left, presum1, presum_dict1)+dfs(root.right, presum2, presum_dict2)+count\n",
    "            \n",
    "        \n",
    "        presum0 = [0]\n",
    "        presum_dict = {0:1}\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            return dfs(root, presum0, presum_dict)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "\n",
    "        result = 0\n",
    "\n",
    "        def search(root):\n",
    "            nonlocal result\n",
    "            if root is None:\n",
    "                return []\n",
    "            paths = [[root.val]]\n",
    "            left_paths = search(root.left)\n",
    "            right_paths = search(root.right)\n",
    "            for left_path in left_paths:\n",
    "                paths.append(left_path+[root.val])\n",
    "            for right_path in right_paths:\n",
    "                paths.append(right_path+[root.val])\n",
    "            for path in paths:\n",
    "                if sum(path) == targetSum:\n",
    "                    result += 1\n",
    "            return paths\n",
    "\n",
    "        search(root)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        self.ans = 0\n",
    "\n",
    "        def check(lst):\n",
    "            total = 0\n",
    "            for i in range(len(lst)-1, -1, -1):\n",
    "                total += lst[i]\n",
    "                if total == targetSum:\n",
    "                    self.ans += 1\n",
    "            return\n",
    "                \n",
    "        def helper(root, lst):\n",
    "            if not root:\n",
    "                return \n",
    "            lst.append(root.val)\n",
    "            check(lst)\n",
    "            r = lst[::]\n",
    "            l = lst[::]\n",
    "            del lst\n",
    "            helper(root.left, r)\n",
    "            helper(root.right, l)\n",
    "            return \n",
    "\n",
    "        helper(root, [])\n",
    "        return self.ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        rootid=id(root)\n",
    "        presum=dict()\n",
    "        prenodes=dict()\n",
    "        presum[0]=0\n",
    "        prenodes[0]=[]\n",
    "\n",
    "        def preorder(node,preid):\n",
    "            nonlocal prenodes\n",
    "            nonlocal presum\n",
    "            nonlocal rootid\n",
    "            if not node:\n",
    "                return\n",
    "\n",
    "            prenodes[id(node)]=prenodes[preid]+[preid]\n",
    "            presum[id(node)]=presum[preid]+node.val\n",
    "            preorder(node.left,id(node))\n",
    "            preorder(node.right,id(node))\n",
    "        \n",
    "        preorder(root,0)\n",
    "        n=0\n",
    "        for nid in presum:\n",
    "            for pid in prenodes[nid]:\n",
    "                if presum[nid]-presum[pid]==targetSum:\n",
    "                    n+=1\n",
    "        return n \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        has_dict = collections.defaultdict(int)\n",
    "        def dfs(cur):\n",
    "            if not cur:\n",
    "                return None\n",
    "            left_sum = dfs(cur.left)\n",
    "            right_sum = dfs(cur.right)\n",
    "            cur_sum = [cur.val]\n",
    "            if left_sum:\n",
    "                for ele in left_sum:\n",
    "                    has_dict[ele] += 1\n",
    "                    cur_sum.append(ele+cur.val)\n",
    "            if right_sum:\n",
    "                for ele in right_sum:\n",
    "                    has_dict[ele] += 1\n",
    "                    cur_sum.append(ele+cur.val)\n",
    "            return cur_sum\n",
    "        root_sum = dfs(root)\n",
    "        if root_sum:\n",
    "            for ele in root_sum:\n",
    "                has_dict[ele] += 1\n",
    "        return has_dict[targetSum]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        # 前缀和\n",
    "        def f(root, pre_sums):\n",
    "            if not root:\n",
    "                return 0\n",
    "            cur_sum = pre_sums[-1] + root.val   # 上一节点的前缀和 + 当前节点的值\n",
    "            cnt = [cur_sum - s == targetSum for s in pre_sums]   # 比较之前所有的段内和满足目标的条数\n",
    "            pre_sums.append(cur_sum)\n",
    "            pre_sums_backup = pre_sums.copy()   # 避免遍历右子树时受到左子树遍历时的影响\n",
    "            return sum(cnt) + f(root.left, pre_sums) + f(root.right, pre_sums_backup)\n",
    "        return f(root, [0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        import copy\n",
    "        arr=[0]\n",
    "        def traceWithP(root,lis):\n",
    "            #print(\"lis is \",lis)\n",
    "            if root==None:\n",
    "                return\n",
    "            v=root.val\n",
    "            if v==targetSum:\n",
    "                arr[0]=arr[0]+1\n",
    "            \n",
    "            temp=v\n",
    "            for p in lis:\n",
    "                temp=temp+p\n",
    "                if temp==targetSum:\n",
    "                    arr[0]=arr[0]+1\n",
    "            \n",
    "            lis=[v]+lis\n",
    "            lis1=copy.deepcopy(lis)\n",
    "            lis2=copy.deepcopy(lis)\n",
    "            traceWithP(root.left,lis1)\n",
    "            traceWithP(root.right,lis2)\n",
    "        \n",
    "        traceWithP(root,[])\n",
    "        return arr[0]\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        paths = list()\n",
    "        def dfs(head, path):\n",
    "            if not head:\n",
    "                return \n",
    "            for i in range(len(path)):\n",
    "                path[i] += head.val \n",
    "                if path[i] == targetSum:\n",
    "                    paths.append(1)\n",
    "            path.append(head.val)\n",
    "            if path[-1] == targetSum:\n",
    "                paths.append(1)\n",
    "            dfs(head.left, path)\n",
    "            dfs(head.right, path)\n",
    "            path.pop()\n",
    "            for i in range(len(path)):\n",
    "                path[i] -= head.val \n",
    "            \n",
    "        dfs(root, [])\n",
    "        return len(paths)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        if root:\n",
    "            result = []\n",
    "            queue = [[[root.val],root]]\n",
    "            while queue:\n",
    "                paths, node = queue.pop(0)\n",
    "                i = 0\n",
    "                while i < len(paths):\n",
    "                    if (sum(paths[i:]) == targetSum):\n",
    "                        result.append(paths)\n",
    "                    i += 1\n",
    "                paths1 = paths.copy()\n",
    "                paths2 = paths.copy()\n",
    "                if node.left:\n",
    "                    paths1.append(node.left.val)\n",
    "                    queue.append([paths1,node.left])\n",
    "                if node.right:\n",
    "                    paths2.append(node.right.val)\n",
    "                    queue.append([paths2,node.right])\n",
    "            return len(result)\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        res=list()\n",
    "        ans=list()\n",
    "        def check(r):\n",
    "            m=r[-1]\n",
    "            if m==targetSum:\n",
    "                ans.append(1)\n",
    "            for i in range(len(r)-1):\n",
    "                if m-r[i]==targetSum:\n",
    "                    ans.append(1)\n",
    "        def fs(temp,listing):\n",
    "            if listing:\n",
    "                now=copy.deepcopy(listing[-1])\n",
    "            else:\n",
    "                now=0\n",
    "            value=temp.val\n",
    "            if not temp.left and not temp.right:\n",
    "                check(listing+[now+value])\n",
    "                res.append(listing+[now+value])\n",
    "                return \n",
    "            check(listing+[now+value])\n",
    "            if temp.left:\n",
    "                fs(temp.left,listing+[now+value])\n",
    "            if temp.right:\n",
    "                fs(temp.right,listing+[now+value])\n",
    "        \n",
    "        fs(root,[])\n",
    "        print(res)\n",
    "        \n",
    "        return sum(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, total: int) -> List[List[int]]:\n",
    "        res=0\n",
    "        \n",
    "        def dfs(root: TreeNode, total: int):\n",
    "            nonlocal res\n",
    "            if not root:\n",
    "                return\n",
    "            path.append(root.val)\n",
    "            total -= root.val\n",
    "            if total == 0:\n",
    "                res+=1\n",
    "            dfs(root.left, total)\n",
    "            dfs(root.right, total)\n",
    "        \n",
    "        def dfs2(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root,total)\n",
    "            dfs2(root.left)\n",
    "            dfs2(root.right)\n",
    "        \n",
    "        dfs2(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        @cache\n",
    "        def dfs(root, total):\n",
    "            if not root:\n",
    "                return 0 \n",
    "            ans = 0\n",
    "            if root.val == total:\n",
    "                ans += 1\n",
    "            ans += dfs(root.left, total - root.val) + dfs(root.right, total - root.val)\n",
    "            return ans\n",
    "        if not root:\n",
    "            return 0\n",
    "        return self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum) + dfs(root, targetSum)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        ans = []\n",
    "        def J(s, r):\n",
    "            sum = 0\n",
    "            for i in range(len(s) - 1, -1, -1):\n",
    "                sum += s[i]\n",
    "                if sum == targetSum:\n",
    "                    ans.append(1)\n",
    "            if not r.left and not r.right:\n",
    "                return\n",
    "            else:\n",
    "                if r.left:\n",
    "                    J(s + [r.left.val], r.left)\n",
    "                if r.right:\n",
    "                    J(s + [r.right.val], r.right)\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "        J([root.val], root)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.count = 0\n",
    "    def pathSum(self, root: TreeNode, target: int) -> int:\n",
    "        def sub_sum(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            root_sum = np.array([root.val])\n",
    "            if root.left:\n",
    "                left_sum = sub_sum(root.left) + root.val\n",
    "                root_sum = np.concatenate((root_sum, left_sum))\n",
    "            if root.right:\n",
    "                right_sum = sub_sum(root.right) + root.val\n",
    "                root_sum = np.concatenate((root_sum, right_sum))\n",
    "            self.count += np.where(root_sum == target)[0].shape[0]\n",
    "            return root_sum\n",
    "        sum_array = sub_sum(root)\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, sum: int) -> int:\n",
    "        def dfs(root, sumlist):\n",
    "            if root is None: return 0\n",
    "            sumlist = [num + root.val for num in sumlist] + [root.val]\n",
    "            return sumlist.count(sum) + dfs(root.left, sumlist) + dfs(root.right, sumlist)\n",
    "        return dfs(root, [])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        def _travel(root: TreeNode) -> (Counter, Counter):\n",
    "            if root is None:\n",
    "                return Counter(), Counter({})\n",
    "\n",
    "            sub_left, remained_left = _travel(root.left)\n",
    "            sub_right, remained_right = _travel(root.right)\n",
    "\n",
    "            cur = Counter()\n",
    "            cur[root.val] = 1\n",
    "            for k in sub_left:\n",
    "                cur[k + root.val] += sub_left[k]\n",
    "            for k in sub_right:\n",
    "                cur[k + root.val] += sub_right[k]\n",
    "\n",
    "            remained_left.update(remained_right)\n",
    "            remained_left.update(sub_left)\n",
    "            remained_left.update(sub_right)\n",
    "            return cur, remained_left\n",
    "\n",
    "        dist, remained = _travel(root)\n",
    "        return dist[targetSum] + remained[targetSum]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getTargetNum(self,root,targetSum,path_val,index):\n",
    "        if not root:return 0\n",
    "\n",
    "        index+=1\n",
    "        path_val[0:index]+=root.val\n",
    "\n",
    "        root_num=(path_val[0:index]==targetSum).sum()\n",
    "        left_num=self.getTargetNum(root.left,targetSum,path_val,index)\n",
    "        right_num=self.getTargetNum(root.right,targetSum,path_val,index)\n",
    "\n",
    "        path_val[0:index]-=root.val\n",
    "        index-=1\n",
    "        return sum([root_num,left_num,right_num])\n",
    "\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        import numpy\n",
    "        return int(self.getTargetNum(root,targetSum,numpy.array([0]*1000),0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        def dfs(root, numlist):\n",
    "            if not root:\n",
    "                return 0\n",
    "            numlist = [num+root.val for num in numlist]\n",
    "            numlist.append(root.val)\n",
    "            count = 0\n",
    "            for i in numlist:\n",
    "                if i == targetSum:\n",
    "                    count += 1\n",
    "            return count + dfs(root.left, numlist) + dfs(root.right, numlist)\n",
    "        return dfs(root, [])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        res = 0\n",
    "\n",
    "        dfs = [(root,{0:1},0)]\n",
    "\n",
    "        while dfs:\n",
    "            node, prefix, last = dfs.pop()\n",
    "            if node is None: continue\n",
    "\n",
    "            new_sum = last + node.val\n",
    "\n",
    "            if new_sum - targetSum in prefix:\n",
    "                res += prefix[new_sum - targetSum]\n",
    "            \n",
    "            if new_sum not in prefix:\n",
    "                prefix[new_sum] = 0\n",
    "            prefix[new_sum] += 1\n",
    "\n",
    "            \n",
    "            dfs.append((node.left, prefix.copy(), new_sum))\n",
    "            dfs.append((node.right, prefix.copy(), new_sum))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        def dfs(root,cur,mp=dict()):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            cur += root.val\n",
    "            ret = 0\n",
    "            if cur - targetSum in mp:\n",
    "                ret += mp[cur - targetSum]\n",
    "            mp = mp.copy()\n",
    "            # print(root.val,cur,mp)\n",
    "            mp[cur] = mp.get(cur,0) + 1\n",
    "            ret += dfs(root.left,cur,mp)\n",
    "            ret += dfs(root.right,cur,mp)\n",
    "            return ret\n",
    "        return dfs(root,cur=0,mp={0:1})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        ans = 0\n",
    "        def dfs(root, record={0:1}, last=0):\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return \n",
    "            if (temp:=last + root.val -targetSum) in record:\n",
    "                # print(root.val, record[temp], record)\n",
    "                ans += record[temp]\n",
    "            new_record = record.copy()\n",
    "            if (temp:=last+root.val) in new_record:\n",
    "                new_record[temp] += 1\n",
    "            else:\n",
    "                new_record[last+root.val] = 1\n",
    "            dfs(root.left, new_record, last+root.val)\n",
    "            dfs(root.right, new_record,last+root.val)\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "\n",
    "        count = collections.defaultdict(int)\n",
    "        count[0]+=1\n",
    "\n",
    "        self.ans = 0\n",
    "\n",
    "\n",
    "        def dfs(node, curr_sum, targetSum, count):\n",
    "            if not node:\n",
    "                return \n",
    "\n",
    "            curr_sum+=node.val\n",
    "            if curr_sum-targetSum in count:\n",
    "                self.ans+=count[curr_sum-targetSum]\n",
    "            count[curr_sum]+=1\n",
    "            count_ = copy.deepcopy(count)\n",
    "\n",
    "            dfs(node.left, curr_sum, targetSum, count)\n",
    "            dfs(node.right, curr_sum, targetSum, count_)\n",
    "            \n",
    "            # self.count[curr_sum]-=1\n",
    "            # curr_sum-=node.val\n",
    "\n",
    "        dfs(root, 0, targetSum, count)\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import copy\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def sumnode(self, node, fsum):\n",
    "        node.val += fsum\n",
    "        if node.left:\n",
    "            self.sumnode(node.left, node.val)\n",
    "        if node.right:\n",
    "            self.sumnode(node.right, node.val)\n",
    "        return node\n",
    "\n",
    "    def dfs(self, node, cache):\n",
    "  \n",
    "        \n",
    "        if node.val in cache: \n",
    "            self.count += cache[node.val]\n",
    "        if node.val == self.targetSum:\n",
    "            self.count += 1\n",
    "        cache[self.targetSum+node.val] += 1\n",
    "        copy_cache = cache.copy()\n",
    "        # print(cache)\n",
    "        if node.left:\n",
    "            self.dfs(node.left, cache)\n",
    "        if node.right:\n",
    "            self.dfs(node.right, copy_cache)\n",
    "        \n",
    "\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        root = self.sumnode(root, 0)\n",
    "        print(root)\n",
    "    \n",
    "        self.count = 0\n",
    "        self.targetSum = targetSum\n",
    "        cache = defaultdict(int)\n",
    "        self.dfs(root, cache)\n",
    "        \n",
    "        return self.count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import copy\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def sumnode(self, node, fsum):\n",
    "        node.val += fsum\n",
    "        if node.left:\n",
    "            self.sumnode(node.left, node.val)\n",
    "        if node.right:\n",
    "            self.sumnode(node.right, node.val)\n",
    "        return node\n",
    "\n",
    "    def dfs(self, node, cache):\n",
    "  \n",
    "        \n",
    "        if node.val in cache: \n",
    "            self.count += cache[node.val]\n",
    "        if node.val == self.targetSum:\n",
    "            self.count += 1\n",
    "        cache[self.targetSum+node.val] += 1\n",
    "        copy_cache = cache.copy()\n",
    "        if node.left:\n",
    "            self.dfs(node.left, cache)\n",
    "        if node.right:\n",
    "            self.dfs(node.right, copy_cache)\n",
    "        \n",
    "\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        root = self.sumnode(root, 0)\n",
    "        print(root)\n",
    "    \n",
    "        self.count = 0\n",
    "        self.targetSum = targetSum\n",
    "        cache = defaultdict(int)\n",
    "        self.dfs(root, cache)\n",
    "        \n",
    "        return self.count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        res = 0\n",
    "\n",
    "        def dfs(root, targetSum, cur_sum, parti_seg_sum):\n",
    "            if not root:\n",
    "                return\n",
    "\n",
    "            nonlocal res\n",
    "            cur_sum += root.val\n",
    "\n",
    "            print(f'cur_sum: {cur_sum}')\n",
    "            print(f'cur_sum - targetSum: {cur_sum - targetSum}')\n",
    "            print(f'parti_seg_sum: {parti_seg_sum}')\n",
    "\n",
    "            if (cur_sum - targetSum) in parti_seg_sum:\n",
    "                res += parti_seg_sum[cur_sum - targetSum]\n",
    "\n",
    "            if cur_sum not in parti_seg_sum:\n",
    "                parti_seg_sum[cur_sum] = 1\n",
    "            else:\n",
    "                parti_seg_sum[cur_sum] += 1\n",
    "\n",
    "            dfs(root.left, targetSum, cur_sum, parti_seg_sum.copy())\n",
    "            dfs(root.right, targetSum, cur_sum, parti_seg_sum.copy())\n",
    "\n",
    "        dfs(root, targetSum, 0, {0: 1})\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getTargetNum(self,root,targetSum,path_val,index):\n",
    "        import copy\n",
    "\n",
    "        if not root:return 0\n",
    "        index+=1\n",
    "        pre=copy.deepcopy(path_val[0:index])\n",
    "        path_val[0:index]+=root.val\n",
    "\n",
    "        root_num=(path_val[0:index]==targetSum).sum()\n",
    "        left_num=self.getTargetNum(root.left,targetSum,path_val,index)\n",
    "        right_num=self.getTargetNum(root.right,targetSum,path_val,index)\n",
    "\n",
    "        path_val[0:index]=pre\n",
    "        index-=1\n",
    "        return sum([root_num,left_num,right_num])\n",
    "\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        import numpy\n",
    "        return int(self.getTargetNum(root,targetSum,numpy.array([0]*1000),0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, node, path, sumList, target):\n",
    "        res = 0\n",
    "        sumList += [0]\n",
    "        for i in range(len(sumList)):\n",
    "            sumList[i] += node.val\n",
    "            if sumList[i] == target:\n",
    "                res += 1\n",
    "        print(\"path:\"+str(path)+\" sumList:\"+str(sumList))\n",
    "        if node.left:\n",
    "            res += self.dfs(node.left, path+[node.left.val], list(sumList), target)\n",
    "        if node.right:\n",
    "            res += self.dfs(node.right, path+[node.right.val], list(sumList), target)\n",
    "        return res\n",
    "\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        return self.dfs(root, [root.val], [], targetSum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "        if not root: return 0\n",
    "        self.cnt = Counter()\n",
    "        def dfs(node, prefix):\n",
    "            if not node:\n",
    "                return \n",
    "            self.cnt[node.val] += 1\n",
    "            tmp = [node.val]\n",
    "            for num in prefix:\n",
    "                num += node.val\n",
    "                self.cnt[num] += 1\n",
    "                tmp.append(num)\n",
    "            # print(tmp)\n",
    "            dfs(node.left, tmp)\n",
    "            dfs(node.right, tmp)\n",
    "        dfs(root, [])\n",
    "        return self.cnt[targetSum]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "count = 0\n",
    "class Solution:\n",
    "    def pathSum(self, root: TreeNode, targetSum: int) -> int:\n",
    "\n",
    "        def dfs(cur,target,preSum):\n",
    "            if not cur:return 0\n",
    "            count= preSum.count(target - cur.val)\n",
    "            preSum =[0]+[i+cur.val for i in preSum[1:]]+[cur.val]\n",
    "            count+=dfs(cur.left,target,preSum.copy())\n",
    "            count+=dfs(cur.right,target,preSum.copy())\n",
    "            \n",
    "            return count\n",
    "        \n",
    "        return dfs(root,targetSum,[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def find(self,root,pre,summ,dic,count,targetSum):\n",
    "        pre = pre.copy()\n",
    "        dic = dic.copy()\n",
    "        if root == None:\n",
    "            return\n",
    "        summ = summ+root.val\n",
    "        pre.append(summ)\n",
    "        if summ in dic.keys():\n",
    "            count[0]+=dic[summ]\n",
    "        if summ+targetSum in dic.keys():\n",
    "            dic[summ+targetSum]+=1\n",
    "        else:\n",
    "            dic[summ+targetSum] = 1\n",
    "        self.find(root.left,pre,summ,dic,count,targetSum)\n",
    "        self.find(root.right,pre,summ,dic,count,targetSum)\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        count = [0]\n",
    "        dic = {}\n",
    "        dic[targetSum] = 1\n",
    "        pre = [0]\n",
    "        summ = 0\n",
    "        self.find(root,pre,summ,dic,count,targetSum)\n",
    "        return count[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        res = []\n",
    "        def dfs(node):\n",
    "            nonlocal res\n",
    "            if not node:\n",
    "                return []\n",
    "            ans = [node.val]\n",
    "            for i in dfs(node.left):\n",
    "                ans.append(i+node.val)\n",
    "            for i in dfs(node.right):\n",
    "                ans.append(i+node.val)\n",
    "            res.extend(ans)\n",
    "            return ans \n",
    "        dfs(root)\n",
    "        return res.count(targetSum)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        stack = []\n",
    "        count = 1 if root.val == targetSum else 0\n",
    "        p = root\n",
    "        p.val = [p.val]\n",
    "        while p or stack:\n",
    "            if p:\n",
    "                stack.append(p)\n",
    "                parent = p\n",
    "                p = p.left\n",
    "                if p:\n",
    "                    if p.val == targetSum:\n",
    "                        count += 1\n",
    "                    l = []\n",
    "                    for v in parent.val:\n",
    "                        l.append(p.val+v)\n",
    "                        if p.val+v == targetSum:\n",
    "                            count += 1\n",
    "                    p.val = [p.val]+l\n",
    "            else:\n",
    "                node = stack.pop()\n",
    "                parent = node\n",
    "                p = node.right\n",
    "                if p:\n",
    "                    if p.val == targetSum:\n",
    "                        count += 1\n",
    "                    l = []\n",
    "                    for v in parent.val:\n",
    "                        l.append(p.val+v)\n",
    "                        if p.val+v == targetSum:\n",
    "                            count += 1\n",
    "                    p.val = [p.val]+l\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        elif not root.left and not root.right:\n",
    "            return int(root.val==targetSum)\n",
    "        res = 0\n",
    "        root.acc_path = [root.val]\n",
    "        \n",
    "        # 现在 root 至少有一个子节点\n",
    "        queue = [root]\n",
    "\n",
    "        while queue:\n",
    "            _n = len(queue)\n",
    "            node = queue.pop(0)\n",
    "            if targetSum in node.acc_path:\n",
    "                res += node.acc_path.count(targetSum)\n",
    "            \n",
    "            if node.left:\n",
    "                node.left.acc_path = [i + node.left.val for i in node.acc_path]\n",
    "                node.left.acc_path.append(node.left.val)\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                node.right.acc_path = [i + node.right.val for i in node.acc_path]\n",
    "                node.right.acc_path.append(node.right.val)\n",
    "                queue.append(node.right)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:\n",
    "        res = 0\n",
    "        def dfs(root, sumlist):\n",
    "            if not root: return 0\n",
    "            sumlist = [num+root.val for num in sumlist]\n",
    "            sumlist.append(root.val)\n",
    "            count = 0\n",
    "            for num in sumlist:\n",
    "                if num == targetSum:\n",
    "                    count += 1\n",
    "            \n",
    "            return count + dfs(root.left, sumlist) + dfs(root.right, sumlist)\n",
    "        \n",
    "        return dfs(root, [])\n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
